package com.yohann.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 * 二叉排序树演示
 * </p>
 *
 * @author Yohann
 * @since 2021/1/9 19:42
 */
public class BinarySearchSortDemo {

    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySearchSort searchSort = new BinarySearchSort();

        for (int i : arr) {
            searchSort.add(new TreeNode(i));
        }

        searchSort.delete(7);
//        searchSort.delete(3);
//        searchSort.delete(10);
//        searchSort.delete(12);
//        searchSort.delete(5);
//        searchSort.delete(1);
//        searchSort.delete(9);
//        searchSort.delete(2);

        //1,3,5,7,9,10,12
        searchSort.display();
    }
}

class BinarySearchSort {
    TreeNode root;

    public void add(TreeNode node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void display() {
        if (root != null) {
            root.infixOrder();
        }
    }

    public void delete(int target) {
        if (root.value == target) {
            if (root.left == null && root.right == null) {
                root = null;
            } else {
                root.delete(root, -1);
            }
        } else {
            root.delete(target);
        }
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                '}';
    }

    //添加节点
    public void add(TreeNode node) {
        if (node == null) {
            return;
        }

        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }

        System.out.println(this);

        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    public void delete(int target) {
        Map<TreeNode, Integer> map = searchNode(target);

        if (map != null) {
            map.forEach(this::delete);
        }
    }

    public void delete(TreeNode parent, int flag) {
        if (flag == 0) {
            /*
            删除父节点的左子节点
            1.叶子节点
            2.只有左子节点
            3.只有右子节点
            4.有两个子节点
             */
            if (parent.left.left == null && parent.left.right == null) {
                parent.left = null;
            } else if (parent.left.left == null) {
                parent.left = parent.left.right;
            } else if (parent.left.right == null) {
                parent.left = parent.left.left;
            } else {
                //找到右子树最小节点
                TreeNode temp = parent.left.left;
                while (temp.right != null) {
                    temp = temp.right;
                }

                //清除最小节点原位置
                delete(temp.value);

                //最小节点代替当前位置
                temp.right = parent.left.right;
                temp.left = parent.left.left;
                parent.left = temp;
            }
        } else if (flag == 1) {
            //删除父节点的右子节点
            if (parent.right.left == null && parent.right.right == null) {
                parent.right = null;
            } else if (parent.right.left == null) {
                parent.right = parent.right.right;
            } else if (parent.right.right == null) {
                parent.right = parent.right.left;
            } else {
                //找到右子树最小节点
                TreeNode temp = parent.right.right;
                while (temp.left != null) {
                    temp = temp.left;
                }

                //清除最小节点原位置
                delete(temp.value);

                //最小节点代替当前位置
                temp.right = parent.right.right;
                temp.left = parent.right.left;
                parent.right = temp;
            }
        } else {
            TreeNode newRoot;
            //删除根节点
            if (parent.right != null) {
                //找到右子树最小节点
                newRoot = parent.right;
                while (newRoot.left != null) {
                    newRoot = newRoot.left;
                }
            } else {
                newRoot = parent.left;
                while (newRoot.right != null) {
                    newRoot = newRoot.right;
                }
            }

            //清除最小节点原位置
            delete(newRoot.value);

            this.value = newRoot.value;
        }
    }

    public Map<TreeNode, Integer> searchNode(int target) {
        if (this.value > target) {
            if (this.left != null) {
                if (this.left.value == target) {
                    Map<TreeNode, Integer> result = new HashMap<>();
                    result.put(this, 0);
                    return result;
                } else {
                    return this.left.searchNode(target);
                }
            }
        } else {
            if (this.right != null) {
                if (this.right.value == target) {
                    Map<TreeNode, Integer> result = new HashMap<>();
                    result.put(this, 1);
                    return result;
                } else {
                    return this.right.searchNode(target);
                }
            }
        }

        return null;
    }
}